Les listes Python ne sont pas des listes chaînées lâches au niveau inférieur, mais plutôt des ArrayList. Le fait central est que leur emplacement en mémoire occupe un espace d'adresses continu. Ce qui est stocké n'est pas l'objet lui-même, mais des références à cet objet références(au niveau du langage C, cela correspond à un pointeur). Cette conception permet une gestion unifiée des données hétérogènes, qu'il s'agisse de tuples de couleurs primaires (RGB) ou de clés cryptographiques complexes (Key), car elles occupent toutes une taille fixe de pointeur.

Mathématiques d'accès et compromis de performance

• $O(1)$ Accès aléatoire: Grâce à la formule $\text{adresse de l'élément} = \text{adresse de départ} + \text{indice} \times \text{taille}$, le CPU peut localiser instantanément.
• Analyse amortie (Amortized Analysis): En utilisant une stratégie de surallocation, bien que l'insertion unique puisse atteindre $O(n)$, la somme totale des coûts $\text{coût total} = n + \sum_{j=0}^{\lg n} 2^j = 3n$, garantit une performance moyenne d'ajout de $O(1)$.
• Limitations d'insertion: Comme indiqué sur la Figure 8-2, l'opération `insert` à tout emplacement nécessite de déplacer tous les pointeurs suivants, ce qui donne une complexité de $O(n)$.